#include<stdio.h>
#include<stdlib.h>
#include "AVL.h"

typedef enum{false, true} bool;

//初始化二叉树
int BBT_Init(BBTree* tree)
{
    tree->root = NULL;
    return true;
}

//创建二叉树,返回指针
BBTree* BBT_Create()
{
    BBTree* pBBTree = (BBTree*)malloc(sizeof(BBTree));
    if(pBBTree == NULL)
        return NULL;
    pBBTree->root = NULL;
    return pBBTree;
}

//创建二叉树节点
BBTNode* CreateTreeNode(ElementType element)
{
    BBTNode* newNode = (BBTNode*)malloc(sizeof(BBTNode));
    if(newNode == NULL)
    {
        printf("CreateTreeNode malloc error!\n");
        return NULL;
    }
    newNode->data = element;
    newNode->bf = element;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

//节点处右单旋
BBTNode * BBT_RotateRight(BBTNode* node)
{
    BBTNode* t = node->left;//记录node节点的左子树根节点
    node->left = t->right;
    t->right = node;
    return t;
}


//节点处左单旋
BBTNode* BBT_RotateLeft(BBTNode* node)
{
    BBTNode* t = node->right;//记录node节点的右子树根节点
    node->right = t->left;
    t->left = node;
    return t;
}

//节点处左右单旋
BBTNode* BBT_RotateLeftRight(BBTNode* node)
{
    node->left = BBT_RotateLeft(node->left);
    return BBT_RotateRight(node);
}

//节点处右左单旋
BBTNode* BBT_RotateRightLeft(BBTNode* node)
{
    node->right = BBT_RotateRight(node->right);
    return BBT_RotateLeft(node);
}

//获取节点处树高
int BBT_GetNodeHeight(BBTNode* node)
{
    if(node == NULL)//node为空，向上层返回高度0
        return 0;
    int leftHeight = BBT_GetNodeHeight(node->left);
    int rightHeight = BBT_GetNodeHeight(node->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;//取节点处左、右子树高度的家婆大值
}

//插入数据
BBTNode* BBT_InsertData(BBTNode* node, ElementType data)
{
    if(node == NULL)
        node = BBT_CreateTreeNode(data);//node节点为空，直接存储data
    else if(data < node->data)
    {
        node->left = BBT_InsertData(node->left, data);//递归左子树
        if(BBT_GetNodeHeigth(node->left) - BBT_GetNodeHeigth(node->right) > 1)//左高右低
        {
            if(data < node->left->data)//LL
                node = BBT_RotateRight(node);
            else//LR
                node = BBT_RotateLeftRight(node);
        }
    }
    else
    {
        node->right = InsertData(node->right,data);//递归右子树
        if(BBT_GetNodeHeigth(node->left) - BBT_GetNodeHeigth(node->right) < -1)//左低右高
        {
            if(data < node->right->data)//RL
                node = BBT_RotateRightLeft(node);
            else//RR
                node = BBT_RotateLeft(node);
        }
    }
    return node;
}


void BBT_PrevPrint(struct TreeNode *  node)
{
    if(node != NULL)
    {
        printf("%d ",node->data);
        BBT_PrevPrint(node->left);
        BBT_PrevPrint(node->right);
    }
}

void BBT_MidPrint(struct TreeNode *  node)
{
    if(node != NULL)
    {
        BBT_MidPrint(node->left);
        printf("%d ",node->data);
        BBT_MidPrint(node->right);
    }
}

void BBT_PostPrint(struct TreeNode * node)
{
    if(node != NULL)
    {
        BBT_PostPrint(node->left);
        BBT_PostPrint(node->right);
        printf("%d ",node->data);  
    }
}

int main(int argc, char const *argv[])
{
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    struct TreeNode * root = NULL;
    for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        root = InsertData(root,a[i]);
    }
    
    printf("prev:");
    PrevPrint(root);
    printf("\n");
    printf("mid:");
    MidPrint(root);
    printf("\n");
    printf("post:");
    PostPrint(root);
    printf("\n");
    return 0;
}
